Section: New Results

Geometric Uncertainties

$G^n$ blending multiple surfaces in polar coordinates

Participants : K.-L. Shi, J.-H. Yong, J.-G. Sun, J.-C. Paul.

This paper proposes a method of $G^n$ blending multiple parametric surfaces in polar coordinates. It models the geometric continuity conditions of parametric surfaces in polar coordinates and presents a mechanism of converting a Cartesian parametric surface into its polar coordinate form. The basic idea is first to re-parameterize the parametric blendees into the form of polar coordinates. Then they are blended simultaneously by a basis function in the complex domain. To extend its compatibility, we also propose a method of converting polar coordinate blending surface into N NURBS patches. One application of this technique is to fill N-sided holes. Examples are presented to show its feasibility and practicability [6] .

Filling n-sided regions with $G^1$ triangular Coons B-spline patches

Participants : K.-L. Shi, J.-H. Yong, J.-G. Sun, J.-C. Paul, H.-J. Gu.

Filling n-sided regions is an essential operation in shape and surface modeling. Positional and tangential continuities are highly required in designing and manufacturing. We propose a method for filling n-sided regions with untrimmed triangular Coons B-spline patches, preserving $G^1$ continuity exactly. The algorithm first computes a central point, a central normal, the central, and the corner derivative vectors. Then the region is split into n triangular areas by connecting the central point to each corner of the boundary. These inner curves and all cross-boundary derivatives are computed fulfilling $G^1$ compatibility conditions. And finally, the triangular patches are generated in the Coons B-spline form, one boundary of which is regressed to the central vertex. Neither positional nor tangential error is introduced by this method. And only one-degree elevation is needed  [54] .

$G^n$ Filling orbicular N-sided holes using periodic B-spline surfaces

Participants : K.-L. Shi, J.-H. Yong, J.-C. Paul.

The orbicular N-sided hole filling problem is usually introduced by filleting an end-point of a part with large radius. The existing methods based on quadrilateral partition or constrained-optimization can rarely generate high-order continuous blending surfaces under these circumstances. This paper first reparameterizes the boundary of the specified orbicular N-sided hole to ensure the compatibility of neighboring cross-boundary derivatives on the connecting points, preserving their $G^n$ continuity. Then we compute the control points of the periodic B-spline surface using the sufficient $G^n$ continuity condition on the pole and the algorithm of extending parametric surfaces. This method generates single blending surface, which can be converted into standard B spline surface by adding knots without introducing errors. It only elevates the degree of the boundary by n. The construction method is simple and efficient, without iteration nor large-scale matrix solving. It achieves $G^n$ continuity under compatible conditions. The blending examples underline its feasibility and practicability  [55] .

A Thin-plate CAD Mesh Model Splitting Approach Based on Fitting Primitives

Participants : Chun Geng, Hiromasa Suzuki, Dong-Ming Yan, Takasi Michikawa, Yuichi Sato, Masayoshi Hashima, Eiji Ohta.

Extracting structural information from mesh models iscrucial for Simulation Driven Design (SDD) in industrialapplications. Focusing on thinplate CAD mesh models (the most commonly used parts in electronic productssuch as PCs, mobile phones and so on), we present an algorithm based on primitive fitting for segmentingthinplate CAD mesh models into parts of three different types, twoof which are extruding surfaces andthe other is a lateral surface. This method can be used for solid model reconstruction in the SDD proces.Our approach involves two steps. First, a completely automatic method for accurate primitive fitting onCAD meshes is proposed based on the hierarchical primitive fitting framework. In the second step, a novelprocedure is proposed for splitting thinplate CAD mesh models by detecting parallel extruding surfaces and lateralsurfaces. The method presented here has been proved to work smoothly in applications of real product design  [46] .

A face-based shape matching method for IGES surface model

Participants : Kaimo Hu, Bin Wang, Yi Gao, Qiming Yuan, Junhai Yong.

IGES is a widely used standard for mechanical data exchange. In this paper, we present a new method for the retrieval task of IGES surface model. Based on this method, a novel distinctive face selection strategy is proposed and evaluated. In the training database, each model is treated as a set of disordered faces, and their features are extracted and stored respectively. The Discounted Cumulative Gain (DCG) value of each face is then calculated and stored for later utilization. To retrieve models in the testing database, we first forecast each face’s DCG value by searching its most similar face’s DCG value in training database, and then the top k faces with highest forecasted DCGs are selected as query input. A greedy algorithm is finally applied to get the total similarity. Experimental results show that our algorithm is superior or at least comparable to some of the most powerful methods in finding parts with similar functionality in most cases  [48] .

Generating B-spline curves based on control-point interpolation

Participants : Jing Liu, Kan-Le Shi, Jun-Hai Yong, He-Jin Gu.

Generating smooth B-spline curves is a fundamental operation of computer aided geometric design. This paper presents a method to calculate unknown control points using specified control points and knots to generate a smooth B-spline curve. It is based on the basis-function-maximum-value parameterization introduced in this paper. This method first parameterizes all control points; then regards given control points as data points to create a fit curve by interpolation; and finally obtains the unknown control points by evaluating the corresponding parameters directly, which ensures the continuity and smoothness of the generated B-spline curve. The examples in the last section illustrate the feasibility of this method  [51] .

A new functionality-based benchmark for basic CAD Model retrieval

Participants : Kaimo Hu, Bin Wang, Yi Gao, Dong Li, Junhai Yong.

In this paper, we propose a new functionality-based benchmark for CAD model retrieval. Our benchmark contains 1968 frequently-used CAD models which are divided into training set and test set. The models are carefully classified by their functionalities in industry. Eight different shape descriptors are then compared using four famous evaluation measurements. The results show that models having the same functionalities do not necessarily share the same or similar shapes, hence the functionality-based retrieval methods are encouraged, which we believe will be of great help for the improvements of design reusability. Some possible future work for 3D model retrieval in mechanical domain are also proposed based on the observation of our experiments  [47] .

Shape similarity assessment approach for CAD models based on graph edit distance

Participants : Bin Wang, Dong Li, Kaimo Hu, Hui Zhang.

This paper proposes a new shape similarity assessment approach for CAD models in Boundary Representation (Brep) based on graph edit distance. A suboptimal computational procedure is performed to find the best alignment between local structures sets of attributed graphs derived from models. Assuming that only a minority of local structures characterize the functionality, we figure out the weight of every local structure in the query model through a training phase, and then evaluate the similarity between two models by calculating the weighted graph edit distance of corresponding attributed graphs. Experiment results show that our method provides solid retrieval performance on a real-world CAD model database  [57] .

The transition between sharp and rounded features and the manipulation of incompatible boundary in filling n-sided holes

Participants : Kan-Le Shi, Jun-Hai Yong, Peng Liu, Jia-Guang Sun, Jean-Claude Paul.

N-sided hole filling plays an important role in vertex blending. Piegl and Tiller presented an algorithm to interpolate the given boundary and cross-boundary derivatives in B-spline form. To deal with the incompatible cases that their algorithm cannot handle, we propose an extension method to manipulate the transition between sharp and rounded features. The algorithm first patches n crescent-shaped extended surfaces to the boundary with $G^2$ continuity to handle incompatibility problem in the corners. Then, we compute the inner curves and the corresponding cross-boundary derivatives fulfilling tangent and twist compatibilities. The generated B-spline Coons patches are $G^1$-continuously connected exactly, and have $\epsilon -G^1$ continuity with the extended surfaces. Our method improves the continuity-quality of the shape and reduces the count of the inserted knots. It can be applied to all $G^0$-continuous boundary conditions without any restrictions imposed on the boundary or cross-boundary derivatives. It generates better shapes than some popular industrial modeling systems on these incompatible occasions. Some examples underline its feasibility  [53] .

Epsilon-G2 B-spline surface interpolation

Participants : Kan-Le Shi, Jun-Hai Yong, Jia-Guang Sun, Jean-Claude Paul.

This paper proposes a method to construct a B-spline surface that interpolates the specified four groups of boundary derivative curves in the B-spline form. The discontinuity can be bounded by an arbitrary geometric invariant as the tolerance. The method first handles the six types of the compatibility problems by continuity-preserving reparameterization, knot-insertion and local control-point tuning. The transformed boundary conditions are then parametrically compatible, so the Coons strategy can be applied to construct the final interpolant. Not only can it be used in the reliable geometric modeling, but the approach also can be applied to many other algorithms that require compatibility guarantee [26] .

$G^2$ B-spline interpolation to a closed mesh

Participants : K.-L. Shi, J.-H. Yong, J.-G. Sun, J.-C. Paul.

This paper focuses on interpolating vertices and normal vectors of a closed quad-dominant mesh 1G2-continuously using regular Coons B-spline surfaces, which are popular in industrial CAD/CAM systems. We first decompose all non-quadrangular facets into quadrilaterals. The tangential and second-order derivative vectors are then estimated on each vertex of the quads. A least-square adjustment algorithm based on the homogeneous form of G2 continuity condition is applied to achieve curvature continuity. Afterwards, the boundary curves, the first- and the second-order cross-boundary derivative curves are constructed fulfilling G2 continuity and compatibility conditions. Coons B-spline patches are finally generated using these curves as boundary conditions. In this paper, the upper bound of the rank of G2 continuity condition matrices is also strictly proved to be 2n−3, and the method of tangent-vector estimation is improved to avoid petal-shaped patches in interpolating solids of revolution [7] .

A new method for identifying and validating features from 2D sectional views

Participants : Yamei Wen, Hui Zhang, Jiaguang Sun, Jean-Claude Paul.

Feature identification is one of the key steps for 3D solids reconstruction from 2D vector engineering drawings using the volume-based method. In this paper, we propose a novel method to identify and validate features from sectional views. First, features are classified as explicit features (EPFs) and implicit features (IPFs), which are then identified in an order of priority using heuristic hints. We show that the problem of constructing EPFs can be formulated as a 0-1 integer linear program (ILP), and the IPFs are generated based on the understanding of semantic information of omitted projections in sectional views. Then, the Loop-Relation Graph (LRG) is introduced as a multi-connected-subgraph representation for describing the relations between loops and features. According to the LRG, a reasoning technique based on confidence is implemented to interactively validate features. This method can recover features without complete projections, and the level of understanding sectional views is improved. Full sections, partial sections, offset sections as well as revolved sections can be handled by our method. Several examples are provided to demonstrate the practicability of our approach [29] .

Ridge extraction of a smooth 2-manifold surface based on vector field

Participants : Wujun Che, Xiaopeng Zhang, Yi-Kuan Zhang, Jean-Claude Paul.

This paper presents a general scheme to compute ridges on a smooth 2-manifold surface from the standpoint of a vector field. A ridge field is introduced. Starting with an initial ridge, which may or may not be umbilical, a ridge line is then traced by calculating an associated integral curve of this field in conjunction with a new projection procedure to prevent it from diverging. This projection is the first that can optimize a ridge guess to lie on a ridge line uniquely and accurately. In order to follow this scheme, we not only develop practical ridge formulae but also address their corresponding computational procedures for an analytical surface patch, especially for an implicit surface. In contrast to other existing methods, our new approach is mathematically sound and characterized by considering the full geometric structures and topological patterns of ridges on a generic smooth surface. The resulting ridges are accurate in the numerical sense and meet the requirement of high accuracy with complete topology. Although the objective of this paper is to develop a mathematically sound framework for ridges on a smooth surface, we give a comprehensive review of relevant works on both meshes and smooth surfaces for readers [11] .

Manifold-ranking based retrieval using $k$-regular nearest neighbor graph

Participants : Bin Wang, Feng Pan, Kaimo Hu, Jean-Claude Paul.

Manifold-ranking is a powerful method in semi-supervised learning, and its performance heavily depends on the quality of the constructed graph. In this paper, we propose a novel graph structure named $k$-regular nearest neighbor ($k$-RNN) graph as well as its constructing algorithm, and apply the new graph structure in the framework of manifold-ranking based retrieval. We show that the manifold-ranking algorithm based on our proposed graph structure performs better than that of the existing graph structures such as $k$-nearest neighbor ($k$-NN) graph and connected graph in image retrieval, 2D data clustering as well as 3D model retrieval. In addition, the automatic sample reweighting and graph updating algorithms are presented for the relevance feedback of our algorithm. Experiments demonstrate that the proposed algorithm outperforms the state-of-the-art algorithms [9] .

Efficient computation of clipped Voronoi diagram for mesh generation

Participants : Dong-Ming Yan, Wenping Wang, Bruno Lévy, Yang Liu.

The Voronoi diagram is a fundamental geometric structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact domain (i.e. a bounded and closed 2D region or 3D volume), some Voronoi cells of their Voronoi diagram are infinite or partially outside of the domain, but in practice only the parts of the cells inside the domain are needed, as when computing the centroidal Voronoi tessellation. Such a Voronoi diagram confined to a compact domain is called a clipped Voronoi diagram. We present an efficient algorithm for computing the clipped Voronoi diagram for a set of sites with respect to a compact 2D region or a 3D volume. We also apply the proposed method to optimal mesh generation based on the centroidal Voronoi tessellation [30] .

Automatic Generation of Canonical Views for CAD Models

Participants : Kaimo Hu, Bin Wang, Bin Yuan, Junhai Yong.

Selecting the best views for 3D objects is useful for many applications. However, with the existing methods applied in CAD models, the results neither exhibit the 3D structures of the models fairly nor conform to human’s browsing habits. In this paper, we present a robust method to generate the canonical views of CAD models, and the above problem is solved by considering the geometry and visual salient features simultaneously. We first demonstrate that for a CAD model, the three coordinate axes can be approximately determined by the scaled normals of its faces, such that the pose can be robustly normalized. A graph-based algorithm is also designed to accelerate the searching process. Then, a convex hull based method is applied to infer the upright orientation. Finally, four isometric views are selected as candidates, and the one whose depth image owns the most visual features is selected. Experiments on the Engineering Shape Benchmark (ESB) show that the views generated by our method are pleasant, informative and representative. We also apply our method in the calculation of model rectilinearity, and the results demonstrate its high performance [35] .

Mechanical Parts Retrieval Based on Typical Face Matching

Participants : Yi Gao, Bin Wang, Kaimo Hu, Junhai Yong.

This paper presents a face-based retrieval algorithm to search mechanical parts with similar partial features. The method makes it easier to retrieve models with partial features so as to support early stage reusability. In the training phase, all the faces in the database are trained and assigned with a value indicating their distinction. Trivial faces and atypical ones are removed in this phase to improve online retrieval efficiency. In the query phase, we evaluate the distinction of the input faces by aligning them with faces in the database. A greedy algorithm is finally applied to match the input faces and the faces in the database according to their similarity order. Experimental results show that our method can provide a favorable performance when applied to retrieve the models with common partial features comparing to some other mesh-based methods [18] .

Continuity Transition with a Single Regular Curved-Knot B-Spline Surface

Participants : Kan-Le Shi, Jun-Hai Yong, Jean-Claude Paul, Jia-Guang Sun.

We propose a canonical form of the curved-knot B-spline surface called the regular curved-knot B-spline. On one hand it allows the transition of the knot vectors so that the continuity configurations of the two opposite boundaries can be different. On the other hand, the regular form achieves the simplicity in storage, evaluation and the construction algorithms, and that makes it possible to be applied in the industrial geometric modeling systems. The applications: bridging, multi-sided hole filling and irregular feature modeling, show that it is well suited for modeling complicated objects, such as a transition between sharp and rounded features. Compared with patching numbers of B-splines, it not only increases the inter-surface continuity of the shape, but also reduces the complexity of algorithms [25] .

Meshless quadrangulation by global parameterization

Participants : Er Li, Bruno Lévy, Xiaopeng Zhang, Wu-Jun Che, Weiming Dong, Jean-Claude Paul.

Point cloud is a basic description of discrete shape information. Parameterization of unorganized points is important for shape analysis and shape reconstruction of natural objects. In this paper we present a new algorithm for global parameterization of an unorganized point cloud and its application to the meshing of the cloud. Our method is guided by principal directions so as to preserve the intrinsic geometric properties. After initial estimation of principal directions, we develop a kNN(k-nearest neighbor) graph-based method to get a smooth direction field. Then the point cloud is cut to be topologically equivalent to a disk. The global parameterization is computed and its gradients align well with the guided direction field. A mixed integer solver is used to guarantee a seamless parameterization across the cut lines. The resultant parameterization can be used to triangulate and quadrangulate the point cloud simultaneously in a fully automatic manner, where the shape of the data is of any genus [19] .